class Solution
{
public:
    int minimizeMax(vector<int> &nums, int p)
    {
        // 排序后两两做差，转化为打家劫舍的问题
        sort(nums.begin(), nums.end());
        int n = nums.size() - 1;
        vector<int> diff(n);
        for (int i = 0; i < n; ++i)
        {
            diff[i] = nums[i + 1] - nums[i];
        }

        // 按照打家劫舍的做法，从大到小排除最大值，直到不够选出p个点
        vector<int> id(n);
        // 对索引排序
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j)
             { return diff[i] < diff[j]; });

        int canTakeCount = (n + 1) / 2;
        set<int> noTake{-1, n};

        for (int i = n - 1; i >= 0; --i)
        {
            int maxId = id[i];

            auto it = noTake.lower_bound(maxId);
            int r = *it;
            int l = *(--it);

            // 更新可以打劫的个数
            canTakeCount -= (r - l) / 2;
            canTakeCount += (r - maxId) / 2;
            canTakeCount += (maxId - l) / 2;
            if (canTakeCount < p)
            {
                return diff[maxId];
            }

            noTake.insert(maxId);
        }
        return 0;
    }
};